package com.cty._01_Base._11_MinNumInRotatedArray;

/**
 * @Auther: cty
 * @Date: 2020/7/2 8:33
 * @Description: 面试题11：旋转数组的最小数字
 * 题目：把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。
 * 输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如数组
 * {3, 4, 5, 1, 2}为{1, 2, 3, 4, 5}的一个旋转，该数组的最小值为1。
 * @version: 1.0
 */

public class MinNumInRotatedArray {

    // 二分法查找旋转数组最小值
    public static int min(int[] array, int length) throws Exception {
        if(array==null || length==0)
            throw new Exception("Invalid parameters");

        int index1 = 0;
        int index2 = length - 1;
        int indexMid = index1;
        while(array[index1] >= array[index2]){
            // 结束条件
            if(index1 + 1 == index2){
                indexMid = index2;
                break;
            }

            indexMid = (index1 + index2) / 2;
            if(array[index1]==array[indexMid] && array[indexMid]==array[index2])
                return minInOrder(array, index1, index2);

            if(array[indexMid] >= array[index1])
                index1 = indexMid;
            else if(array[indexMid] <= array[index2])
                index2 = indexMid;
        }  // end while

        return array[indexMid];
    }  // end min()

    // 顺序查找数组中最小值
    private static int minInOrder(int[] array, int index1, int index2){
        int min = index1;
        for(int i=index1; i<=index2; i++)
            if(array[i] < array[min])
                min = i;

        return array[min];
    }  // end minInOrder()

}  // end class
